package com.lwl.Algorithmic_data_structure.class25单调栈;

import com.lwl.Utils.PrintUtil;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author lwl
 * @Description 单调栈，给你一个数组，请你求出每个元素距离最近比他小的元素的位置
 * arr = [ 3, 1, 2, 3, 3]
 * 0  1  2  3
 * [
 * 0 : [-1,  1]
 * 1 : [-1, -1]
 * 2 : [ 1, -1]
 * 3 : [ 2, -1]
 * 4 : [ 2, -1]
 * ]
 * @date 2023/6/25 20:47
 */
public class Code02MonotonousStackWithRepeat {

    public static void main(String[] args) {
//        int[][] array = monotonousStack(new int[]{3, 1, 2, 3, 3});
        /*
         * -1 -1
         * 0 -1
         * 0 -1
         * 1 -1
         */
//        int[][] array = monotonousStack(new int[]{-5, 0, 0, 2});
        int[][] array = monotonousStack1(new int[]{-5, 0, 0, 2});
//        int[][] array = monotonousStack2(new int[]{-5, 0, 0, 2});
        PrintUtil.printArray(array);
    }

    static class Node {
        Integer index;

        Node next;
        Node pre;

        public Node(Integer index) {
            this.index = index;
        }
    }

    /**
     * 使用数组保存重复节点
     */
    public static int[][] monotonousStack2(int[] array) {
        LinkedList<List<Integer>> stack = new LinkedList<>();
        int[][] res = new int[array.length][2];
        for (int i = 0; i < array.length; i++) {
            while (!stack.isEmpty() && array[stack.peekLast().get(0)] > array[i]) {
                List<Integer> pollList = stack.pollLast();
                for (Integer index : pollList) {
                    res[index][0] = stack.isEmpty() ? -1 : stack.peekLast().get(stack.peekLast().size() - 1);
                    res[index][1] = i;
                }
            }
            // 如何和当前栈最后元素相等，则合并到链表中
            if (!stack.isEmpty() && array[i] == array[stack.peekLast().get(0)]) {
                stack.peekLast().add(i);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                stack.addLast(list);
            }
        }
        while (!stack.isEmpty()) {
            List<Integer> pollList = stack.pollLast();
            for (Integer index : pollList) {
                res[index][1] = -1;
                res[index][0] = stack.isEmpty() ? -1 : stack.peekLast().get(stack.peekLast().size() - 1);
            }
        }
        return res;
    }


    /**
     * 使用链表保存重复节点，非僵尸节点，拷贝的方式
     */
    public static int[][] monotonousStack1(int[] array) {
        LinkedList<Node> stack = new LinkedList<>();
        int[][] res = new int[array.length][2];
        for (int i = 0; i < array.length; i++) {
            while (!stack.isEmpty() && array[stack.peekLast().index] > array[i]) {
                Node pollNode = stack.pollLast();
                while (pollNode != null) {
                    res[pollNode.index][0] = stack.isEmpty() ? -1 : stack.peekLast().index;
                    res[pollNode.index][1] = i;
                    pollNode = pollNode.next;
                }
            }
            // 如何和当前栈最后元素相等，则合并到链表中
            if (!stack.isEmpty() && array[i] == array[stack.peekLast().index]) {
                Node node = new Node(i);
                Node t = stack.peekLast();
                Node tCopy = new Node(t.index);
                tCopy.next = t.next;
                tCopy.pre = t.pre;
                t = node;
                node.next = tCopy;
                tCopy.pre = node;
            } else {
                stack.addLast(new Node(i));
            }
        }
        while (!stack.isEmpty()) {
            Node pollNode = stack.pollLast();
            while (pollNode != null) {
                res[pollNode.index][1] = -1;
                res[pollNode.index][0] = stack.isEmpty() ? -1 : stack.peekLast().index;
                pollNode = pollNode.next;
            }
        }
        return res;
    }

    /**
     * 使用链表保存重复节点，僵尸节点
     */
    public static int[][] monotonousStack(int[] array) {
        LinkedList<Node> stack = new LinkedList<>();
        int[][] res = new int[array.length][2];
        for (int i = 0; i < array.length; i++) {
            while (!stack.isEmpty() && array[stack.peekLast().next.index] > array[i]) {
                Node pollNode = stack.pollLast();
                while (pollNode != null) {
                    if (pollNode.index == null) {
                        pollNode = pollNode.next;
                        continue;
                    }
                    res[pollNode.index][0] = stack.isEmpty() ? -1 : stack.peekLast().next.index;
                    res[pollNode.index][1] = i;
                    pollNode = pollNode.next;
                }
            }
            // 如何和当前栈最后元素相等，则合并到链表中
            if (!stack.isEmpty() && array[i] == array[stack.peekLast().next.index]) {
                Node t = stack.peekLast().next;
                Node node = new Node(i);
                stack.peekLast().next = node;
                node.pre = stack.peekLast();
                node.next = t;
                t.pre = node;
            } else {
                Node 僵尸节点 = new Node(null);
                Node node = new Node(i);
                僵尸节点.next = node;
                node.pre = 僵尸节点;
                stack.addLast(僵尸节点);
            }
        }
        while (!stack.isEmpty()) {
            Node pollNode = stack.pollLast();
            while (pollNode != null) {
                if (pollNode.index == null) {
                    pollNode = pollNode.next;
                    continue;
                }
                res[pollNode.index][1] = -1;
                res[pollNode.index][0] = stack.isEmpty() ? -1 : stack.peekLast().next.index;
                pollNode = pollNode.next;
            }
        }
        return res;
    }

}
